import java.util.Arrays;
import java.util.Random;

public class ShellSort {
    /*
    * 时间复杂度和增量有关系，所以无法得出准确的时间复杂度
    * 但只需要记住：在一定的范围里，希尔排序的时间复杂度为 O(N^1.3 ~ N^1.5)
    * 空间复杂度为 O(1)
    * */
    public static void shell(int[] array,int group){
        for (int i = group; i < array.length; i += 1) {
            int tmp = array[i];
            int j = i-group;
            for (; j >= 0; j-=group) {
                if(tmp < array[j]){
                    array[j+group] = array[j];
                }else{
                    break;
                }
            }
            array[j+group] = tmp;
        }
    }
    public static void shellSort(int[] array){
        int group = array.length;
        // 预排序
        while(group > 1){
            // 第一次分组委 数组的长度，即 头尾判断。
            // 其后，每次分组个数，缩小一倍。
            shell(array,group);
            group /= 2;
        }
        // 最后调整
        shell(array,1);
    }
    // 有序
    public static void test1(int capacity){
        int[] array = new int[capacity];
        for (int i = 0; i < capacity; i++) {
            array[i] = i;
        }
        long start = System.currentTimeMillis();
        shellSort(array);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }

    // 无序
    public static void test2(int capacity){
        int[] array = new int[capacity];
        Random random = new Random();
        for (int i = 0; i < capacity; i++) {
            array[i] = random.nextInt(capacity);
        }
        long start = System.currentTimeMillis();
        shellSort(array);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
    }


    public static void main(String[] args) {
        test1(10000);
        test2(10000);
    }
}
